c.1200, anes, from ane "one" (see one ) + adverbial genitive. Replaced Old English æne. Spelling changed as pronunciation shifted from two syllables to one after c.1300. Pronunciation change to "wuns" parallels that of one. As an emphatic, meaning "once and for all," it is attested from c.1300, but this now is regarded as a Pennsylvania German dialect formation. Meaning "in a past time" (but not necessarily just one time) is from mid-13c.
Once upon a time as the beginning of a story is recorded from 1590s. At once originally (early 13c.) meant "simultaneously," later "in one company" (c.1300), and preserved the sense of "one" in the word; the phrase typically appeared as one word, atones; the modern meaning "immediately" is attested from 1530s.
Old English eall "all, every, entire," from Proto-Germanic *alnaz (cf. Old Frisian, Old High German al, Old Norse allr, Gothic alls), with no certain connection outside Germanic.
Combinations with all meaning "wholly, without limit" were common in Old English (e.g. eall-halig "all-holy," eall-mihtig "all-mighty") and the method continued to form new compound words throughout the history of English. First record of all out "to one's full powers" is 1880. All-terrain vehicle first recorded 1968. All clear as a signal of "no danger" is recorded from 1902. All right, indicative of approval, is attested from 1953.